package __回溯算法

/*
https://leetcode.cn/problems/non-decreasing-subsequences/

491. 非递减子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。
你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
*/
var (
	res491  [][]int
	path491 []int
)

func findSubsequences(nums []int) [][]int {
	//初始化数组
	res491, path491 = make([][]int, 0), make([]int, 0, len(nums))

	dfs491(nums, 0)
	return res491
}
func dfs491(nums []int, start int) {
	//如果路径长度 >= 2,开始收集结果
	if len(path491) >= 2 {
		tmp := make([]int, len(path491))
		copy(tmp, path491)
		res491 = append(res491, tmp)
	}
	used := make(map[int]bool, len(nums)) // 初始化used字典，用以对同层元素去重
	//从start位置遍历元素
	for i := start; i < len(nums); i++ {
		if used[nums[i]] { // 去重
			continue
		}
		//如果路径为0 || i元素>=path末尾元素,符合递增
		if len(path491) == 0 || nums[i] >= path491[len(path491)-1] {
			path491 = append(path491, nums[i]) //path路径添加
			used[nums[i]] = true               //状态标记
			dfs491(nums, i+1)                  //递归调用
			path491 = path491[:len(path491)-1] //状态回溯
		}
	}
}
